package com.ly.algorithm.leetcode.BST;


/**
 * @Classname Problem230
 * @Description
 *
 * 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
 *
 * 说明：
 * 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
 *
 * 示例 1:
 *
 * 输入: root = [3,1,4,null,2], k = 1
 *    3
 *   / \
 *  1   4
 *   \
 *    2
 * 输出: 1
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 *        5
 *       / \
 *      3   6
 *     / \
 *    2   4
 *   /
 *  1
 * 输出: 3
 *
 *
 * @Date 2020/12/22 21:04
 * @Author 冷心影翼
 */
public class Problem230 {

	public static void main(String[] args) {
		Solution230 solution230 = new Solution230();
		TreeNode treeNode = new TreeNode(5);
		treeNode.left = new TreeNode(3);
		treeNode.right = new TreeNode(6);
		treeNode.left.left = new TreeNode(2);
		treeNode.left.right = new TreeNode(4);
		treeNode.left.left.left = new TreeNode(1);
		System.out.println(solution230.kthSmallest(treeNode, 4));
	}
}


class Solution230 {
	int count;

	int ans;

	public int kthSmallest(TreeNode root, int k) {
		infixOrder(root,k);
		return ans;
	}

	public void infixOrder(TreeNode root,int k) {
		if(root == null)
			return;
		infixOrder(root.left,k);
		count++;
		if(count == k) {
			ans = root.val;
		}
		infixOrder(root.right,k);
	}

}
